package _18_剑指OfferII;

public class _013_剑指OfferII二维子矩阵的和 {

    int[][] sum;

    public _013_剑指OfferII二维子矩阵的和(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        sum = new int[row + 1][col + 1];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                sum[i + 1][j + 1] += matrix[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
    }

    // 一维前缀和
   /* public _013_剑指OfferII二维子矩阵的和(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        sum = new int[row][col];
        for (int i = 0; i < row; i++) {
            sum[i][0] = matrix[i][0];
            for (int j = 1; j < col; j++) {
                sum[i][j] += sum[i][j - 1] + matrix[i][j];
            }
        }
    }*/

    public int sumRegion1(int row1, int col1, int row2, int col2) {
        int total = 0;
        for (int i = row1; i <= row2; i++) {
            total += sum[i][col1] - col1 > 0? sum[i][col1 - 1]: 0;
        }
        return total;
    }

}
